package leetcode.search;

import java.util.ArrayList;
import java.util.List;

/**
 给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。

 规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。

 请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。

 给定下面的 5x5 矩阵:

 太平洋 ~   ~   ~   ~   ~
 ~  1   2   2   3  (5) *
 ~  3   2   3  (4) (4) *
 ~  2   4  (5)  3   1  *
 ~ (6) (7)  1   4   5  *
 ~ (5)  1   1   2   4  *
 *   *   *   *   * 大西洋

 返回:

 [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).


 */
public class PacificAtlantic417 {
    int []direct = new int[]{-1,0,1,0,-1};

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        int m = heights.length;
        int n = heights[0].length;

        if(m==0 || n==0)
            return new ArrayList<>();

        boolean [][] canRechA = new boolean[m][n];//从大西洋走可以到达的点
        boolean [][] canRechP = new boolean[m][n];//从太平洋走可以到达的点

        for (int i = 0; i < m; i++) {
            dfs(heights,canRechA,i,n-1);//最后一列--大西洋
            dfs(heights,canRechP,i,0);//第一列--太平洋
        }

        for (int i = 0; i < n; i++) {
            dfs(heights,canRechA,m-1,i);//最后一行--大西洋
            dfs(heights,canRechP,0,i);//第一行--太平洋
        }

        ArrayList<List<Integer>> res = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                if(canRechA[i][j] && canRechP[i][j]){
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(i);
                    list.add(j);
                    res.add(list);
                }
            }
        }
        return res;
    }

    private void dfs(int[][]height,boolean[][]rech,int i,int j){
        if(rech[i][j])
            return;
        int m = height.length;
        int n = height[0].length;

        rech[i][j] = true;

        for (int i1 = 0; i1 < direct.length-1; i1++) {
            int x = i+direct[i1];
            int y = j+direct[i1+1];

            if(x>=0 && x<m   &&  y>=0 && y<n &&//越界检查
                    height[x][y]>=height[i][j]){//前一个位置>=当前位置，才能溜过来
                dfs(height,rech,x,y);
            }
        }
    }
}